package com.heima.leetcode.datastructure.binarytree;


import java.util.Arrays;

/**
 * <strong>根据前中遍历结果建树和根据后中遍历结果建树 105 106</strong>
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/8 21:47
 */
public class BuildTreeByTraversal {
    //  一棵树的前序遍历结果和中序遍历结果如下(保证遍历结果中没有重复元素)
    //  pre: {1,2,4,3,6,7}   in:{4,2,1,6,3,7}
    //  => 根节点：1
    //  => 左子树：in:{4,2}     pre:{2,4}
    //  => 右子树：in:{6,3,7}   pre:{3,6,7}
    //
    //  => 左子树根节点: 2
    //  => 左子树的左子节点：4
    //  => 左子树的右子节点：null
    //
    //  => 右子树根节点：3
    //  => 右子树左子节点：6
    //  => 右子树右子节点：7
    //
    //  =>              1
    //                 / \
    //                2   3
    //               /   / \
    //              4   6   7

    /**
     * <h3>根据前序遍历结果和中序遍历结果建立一颗二叉树</h3>
     * @param preOrder 前序遍历的结果
     * @param inOrder 中序遍历的结果
     * @return 建立好的二叉树的根节点
     */
    public static TreeNode buildTreeByPreAndIn(int[] preOrder, int[] inOrder) {
        if (preOrder.length == 0) {
            return null;
        }
        int rootValue = preOrder[0];
        TreeNode root = new TreeNode(rootValue);
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue) {
                int[] leftIn = Arrays.copyOfRange(inOrder, 0, i); // 含头不含尾
                int[] rightIn = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);
                int[] leftPre = Arrays.copyOfRange(preOrder, 1, i + 1);
                int[] rightPre = Arrays.copyOfRange(preOrder, i + 1, preOrder.length);
                root.left = buildTreeByPreAndIn(leftPre, leftIn);
                root.right = buildTreeByPreAndIn(rightPre, rightIn);
                break;
            }
        }
        return root;
    }

    //  一棵树的中序遍历结果和后序遍历结果如下(保证遍历结果中没有重复元素)
    //  post: {4,2,6,7,3,1}   in:{4,2,1,6,3,7}
    //  => 根节点：1
    //  => 左子树：in:{4,2}     post:{4,2}
    //  => 右子树：in:{6,3,7}   pre:{6,7,3}
    //
    //  => 左子树根节点: 2
    //  => 左子树的左子节点：4
    //  => 左子树的右子节点：null
    //
    //  => 右子树根节点：3
    //  => 右子树左子节点：6
    //  => 右子树右子节点：7
    //
    //  =>              1
    //                 / \
    //                2   3
    //               /   / \
    //              4   6   7

    /**
     * 根据中序遍历结果和后序遍历结果构建二叉树
     * @param inOrder 中序遍历结果
     * @param postOrder 后序遍历结果
     * @return 构建好的二叉树的头节点
     */
    public static TreeNode buildTreeByInAndPost(int[] inOrder, int[] postOrder){
        if (inOrder.length == 0){
            return null;
        }
        int rootValue = postOrder[postOrder.length - 1];
        TreeNode root = new TreeNode(rootValue);
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue){
                int[] leftIn = Arrays.copyOfRange(inOrder,0,i);
                int[] rightIn = Arrays.copyOfRange(inOrder,i + 1,inOrder.length);
                int[] leftPost = Arrays.copyOfRange(postOrder,0,i);
                int[] rightPost = Arrays.copyOfRange(postOrder,i,postOrder.length - 1);
                root.left = buildTreeByInAndPost(leftIn,leftPost);
                root.right = buildTreeByInAndPost(rightIn,rightPost);
            }
        }
        return root;
    }
}
